package 栈和队列;

import java.util.Stack;

/**
 * @description:
 * @author: ywk 计算直方图中的最大矩形
 * @date: 2020-06-28
 */
public class CalMaxArea {
    class StackItem{
        public int height;
        public int index;

        public StackItem(int height, int index) {
            this.height = height;
            this.index = index;
        }
    }

    int maxRectangleArea(int A[], int n) {
        int maxArea = 0;
        if (A == null || A.length == 0) {
            return maxArea;
        }
        Stack<StackItem> stack = new Stack<>();
        stack.push(new StackItem(Integer.MIN_VALUE, -1));
        for (int i = 0; i < n; i++) {
            StackItem cur = new StackItem(i < n ? A[i] : Integer.MIN_VALUE, i);
            if (cur.height > stack.peek().height) {
                stack.push(cur);
                continue;
            }
            while (stack.size() > 1) {
                StackItem prev = stack.peek();
                int area = (i - prev.index) * prev.height;
                if (area > maxArea) {
                    maxArea = area;
                }
                prev.height = cur.height;
                if (prev.height > stack.get(stack.size() - 2).height) {
                    break;
                }
                stack.pop();
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        CalMaxArea calMaxArea = new CalMaxArea();
        int[] arr = {3, 2, 5, 6, 6, 4, 4};
        System.out.println(calMaxArea.maxRectangleArea(arr, arr.length));
    }
}
